\section{Introduction}
\label{sec:introduction}

The problem of result-set diversity has been studied in multiple domains, but
perhaps the most robust literature exists in web search.  In search, it is
common to introduce diversity by mixing in different interpretations of a query,
as in \cite{RadlinskiBCJ09}, or by attempting to construct result sets to be
pairwise distant, as in \cite{CarbonellG98}.  The goal in these
instances is largely to cater to the needs of multiple distinct user types, each
of whom enter the same query, but with different goals.  The system may provide
a diverse result set to meet the needs of different types simultaneously, even
though a single user might be happiest with a non-diverse result set.

We study an alternate form of the diversity problem, in which each individual
user prefers a diverse result set, for example to provide ongoing novelty in a
series of entertaining items, or to provide a balance of opinions on a sensitive
topic.

Specifically, we consider the problem of selecting subsets of items that are
simultaneously diverse in multiple dimensions.  This problem arises in a variety
of contexts.  As a toy example, consider the task of selecting the program
committee for this conference.  The chairs are faced with the task of producing
a committee that offers sufficient expertise in all important topics of the
conference, while simultaneously covering different regions of the world,
providing a good mix of gender, seniority, industry versus academia, and so
forth.

Many other examples exist in natural settings. An e-commerce website may wish to
show televisions covering multiple technologies, screen dimensions,
manufacturers, and price points. Or a website offering pre-packaged vacation
travel may be interested in showing customers a small set of options that cover
a wide range of alternatives: domestic or international; cheap or expensive;
family-friendly or romantic; and so on.  Similarly, as an example we will
consider more closely below, consider a system recommending interesting content
to a user.  The system aims to provide content that is simultaneously diverse
along a variety of axes including topic (sports vs. politics vs. technology),
geographic specificity (world news vs. national news), voice (humorous,
scandalous, contrapuntal), and media type (videos vs. blog articles).

Most commonly, it is important to be simultaneously diverse in all dimensions;
in our program committee example, for instance, no amount of diversity in
national origin will rescue the hapless committee constituted entirely of
experts in itemset discovery.  Hence, while we will discuss other metrics, our
results will focus on minimizing the worst-case coverage.

A final distinction arises in this class of diversity problems.  In some cases,
an algorithm may have full access to information about all candidate items.
However in most web/internet based applications, the system must make a
commitment to certain items before other items are available for consideration.
This may occur because candidates truly arrive in an online manner over time, or
because a large dataset is to be processed in a streaming manner, or most
commonly, because each page of results must be produced at the lowest possible
latency.  A user should be provided with a diverse experience over many
pageviews, and perhaps even many sessions, but the first response must be
committed before future requests are known.  Hence, an algorithm that operates
purely in an offline context may not extend naturally to each successive
request.

This variant of the problem arises in content recommendation, news feeds
applications on news websites, search-type interfaces for web search, e-commerce
search (as at \texttt{amazon.com}, item search (as at \texttt{ebay.com}), and so
forth. We are primarily motivated by the problem of providing a stream of
interesting content, where the items need to be presented in a timely manner
with consideration for a variety of attribute features, each of which could have
varying ranges and densities.  Therefore (irrevocable) decisions on whether new
items should be shown or skipped need to be made in an online manner.

We abstract this problem as follows.  A stream of items, each decorated with
features, arrives over time.  As each item arrives, the algorithm must accept or
decline it.  The algorithm must select as many items as specified by a budget,
and its score is the coverage of the least populous feature in the final set.

The content recommendation problem by which we are motivated differs from the
abstract formulation in few key ways; we recap these differences here.  First,
the diversifier will typically have access to constant-size batches of input,
rather than individual items.  However, the asymptotic behavior of our problem
is unchanged in this case, so we may focus our attention on the simpler
variant. Next, the diversifier is required to ``trade off'' diversity with the
quality of items selected into the result set.  There are several natural
mechanisms to incorporate item quality into the formulation, which we describe
later.  Finally, we study coverage of the worst feature, but in certain settings
it may be important to study other variants, such as the average feature.  We
survey the results for other norms, and also present empirical results analyzing
our algorithms with respect to low-performing features other than the worst. 

\medskip
\noindent
{\bf Our Contributions.} 
We now give a high-level overview of the contributions of this paper.
\begin{enumerate}
\item We formalize the problem of online diversification on
  multi-dimensional featured items. In our problem formulation, the objective is
  to maximize the minimum coverage over all features, but we also present simple
  results for other variants of this
  formulation, both in the offline and the online settings 
  (cf. Sections~\ref{sec:functions} and~\ref{sec:problem}).
\item We theoretically analyze our problem formulation by showing
  hardness results for specific small-coverage and adversarial
  input instances. 
  We then present a novel algorithm for the diversification problems 
  and as the main theoretical result of
  our paper (Theorem~\ref{thm:main}), we prove that the algorithm achieves an
  approximation ratio of 50\% on the objective function,
  provided the optimum coverage is large enough, and the 
  items are drawn i.i.d. from some probability distribution (that is unknown to the
  algorithm). The theoretical analysis and techniques
  presented here are novel, and the main algorithm is simple, easy to implement,
  and lightweight, and therefore potentially applicable to a very wide range of
  scenarios (cf. Section~\ref{sec:algorithm}).
\item We perform comprehensive experimental evaluation on real-world Google+ Sparks
  data as well as several synthetically generated data sets. The experimental
  results not only conclusively corroborate our theoretical findings but also
  show that our algorithm performs significantly better than its analytical guarantees on all
  data sets. In fact, the performance of the algorithm is close to optimal for
  the minimum coverage and very good even for subsequent low-coverage
  features (cf. Section~\ref{sec:exp}). Further, the algorithm outperforms a set of
  natural and intuitive algorithms for the diversification problem by a wide margin.
\end{enumerate}

